1. Field of the Invention
The present invention generally relates to estimating the frequency of a sinusoid in noise, and in particular to phase-based approaches to frequency estimation.
2. Background Description
The problem of estimating the frequency of a sinusoid in noise arises in many areas of applied signal processing. It is typically studied by considering a sequence of N samples of a complex sinusoid plus complex white Gaussian noise given by
y1(n)=Aej(xcfx89on+xcex8)+v(n), n=1,2,3 . . . , N,xe2x80x83xe2x80x83(1)
where the amplitude A greater than 0, the frequency xcfx89oxcex5(xe2x88x92xcfx80,xcfx80] radians/sample, and the phase xcex8xcex5[0,2xcfx80) are unknown constants, and the v(n) are samples of a complex-valued, white, zero mean Gaussian noise sequence whose real and imaginary components are uncorrelated and each has variance "sgr"2/2 so that v(n) has variance "sgr"2. The signal-to-noise ratio (SNR) of the problem is defined to be SNR=A2/"sgr"2. The performance of a frequency estimator is typically compared to the Cramer-Rao bound (CRB) for frequency estimation, which is given by                               σ                      ω            0                    2                ≥                              6                                          N                ⁡                                  (                                                            N                      2                                        -                    1                                    )                                            ⁢              SNR                                .                                    (        2        )            
Frequency estimation techniques typically suffer from a threshold effect, where for SNRs above the threshold the variance of the estimate attains the CRB, while for SNRs below the threshold the variance of the estimate rapidly increases. The particular SNR value where this threshold occurs depends on the particular estimation technique. For example, the maximum likelihood estimate (MLE) of frequency achieves the CRB, but only when the SNR is above a certain threshold (see D. C. Rife and R. R. Boorstyn, xe2x80x9cSingle-tone parameter estimation from discrete-time observations,xe2x80x9d IEEE Trans. Inform. Theory, vol. IT-20, pp. 591-598, September 1974, hereinafter Rife and Boorstyn). Although the MLE can be computed by finding the frequency that maximizes the periodogram, this approach is often too computationally complex, even when the periodogram is computed using the fast Fourier transform (FFT).
A more efficient approach based on least-squares fitting of a line to the unwrapped phases of the signal samples was proposed by Tretter (S. A. Tretter, xe2x80x9cEstimating the frequency of a noisy sinusoid by linear regression,xe2x80x9d IEEE Trans. Inform. Theory, vol. IT-31, pp. 832-835, November 1985). His technique was modified by Kay (S. Kay, xe2x80x9cA fast and accurate single frequency estimator,xe2x80x9d IEEE Trans. Acoust., Speech, Signal Processing, vol. 37, pp. 1987-1990, December 1989; hereinafter xe2x80x9cKay""s methodxe2x80x9d) to remove the explicit use of phase unwrapping by performing least-squares processing of the phase differences between signal samples.
Like the MLE, these phase-based methods attain the CRB when the SNR is above a threshold; however, a problem with these phase-based methods is that the threshold is higher than for the MLE. In addition, the standard phase-based frequency estimate has a threshold that increases as the value of the frequency to be estimated moves toward the edges of the interval (xe2x88x92xcfx80,xcfx80] radians/sample; this often limits the frequency range over which estimation can be accurately accomplished. Further, the threshold does not decrease as the number of samples, N, is increased.
Various methods have been proposed to improve the threshold performance of the phase-based methods, and make them behave more like the MLE. Djuric and Kay (P. M. Djuric and S. M. Kay, xe2x80x9cParameter estimation of chirp signals,xe2x80x9d IEEE Trans. Acoust., Speech, Signal Processing, vol. 38, pp. 2118-2126, December 1990; hereinafter xe2x80x9cDjuric and Kayxe2x80x9d) used second-order differences of the phases, rather than the first-order differences used in Kay""s method, to reduce the dependency of the threshold on frequency; the result is a nearly constant threshold across the entire frequency interval (xe2x88x92xcfx80,xcfx80], with the threshold slightly above the level that occurs for midband frequencies for Kay""s method. Actually, the intent of Djuric and Kay was to provide a method for estimating frequency rate as well as frequency; however, the technique they used can be exploited to provide a frequency estimate whose threshold is frequency independent. Alternatively, Kim et al. (D. Kim, M. J. Narasimha, and D. C. Cox, xe2x80x9cAn improved single frequency estimator,xe2x80x9d IEEE Signal Processing Letters, vol. 3, pp. 212-214, July 1996; hereinafter xe2x80x9cKim et al.xe2x80x9d) used a simple finite impulse response (FIR) filter to boost the SNR prior to computing and processing the phases. This reduces the threshold for frequencies near the center of the interval (xe2x88x92xcfx80,xcfx80], but at the expense of further restrictions on the frequency estimation interval.
It is therefore an object of the present invention to provide a frequency estimation method whose performance is independent of frequency.
It is also an object of the invention to reduce the threshold level of SNR required for accurate frequency estimation.
Another object of the invention is to provide a method whose threshold decreases with an increasing number of samples.
It is a further object of the invention to allow phase-based estimation of multiple sinusoids.
It is also an object of the invention to accomplish the foregoing objects in a computationally efficient manner.
The method in accordance with the invention combines the frequency-independent threshold characteristic of Djuric and Kay with the lowered threshold characteristic of Kim et al.; the cost is modest additional computational complexity. The computational expense of this improvement is roughly 1.25 times as many multiplies and 1.5 times as many adds as are required by Kay""s method, half as many arctangents as are required by Kay""s method, and four compares (no compares are needed in Kay""s method); also, the technique can be implemented in parallel to reduce the time required. The invention applies the filter used in Kim et al. to overlapping frequency bands that cover (xe2x88x92xcfx80,xcfx80], detects which band the sinusoid is in, and then processes the phases of the detected band""s output signal using Kay""s method. The key to making this method work is to properly choose the frequency bands and to recognize that the filter outputs can be decimated before performing further processing.
This specification shows that the threshold performance and the frequency range of the phase-based frequency estimation can be extended simultaneously by applying filter bank processing prior to implementing the phase-based frequency estimation technique. In principle, the processing consists of creating three auxiliary signals by modulating the original signal and then applying the results of Kim et al. to the original signal as well as each of the three auxiliary signals. This can be viewed as applying the original signal to a highly overlapped four-channel filter bank, detecting which channel contains the sinusoid, and then applying phase-based frequency estimation to the selected channel. However, in practice, the key to making this approach computationally viable is four-fold: (i) the creation of the auxiliary signals requires a negligible amount of additional processing, (ii) the filter used to implement the filter bank consists of a two-tap FIR filter requiring no multiplies, (iii) the computational complexity can be reduced by developing a closed form for the frequency estimate given in Kim et al. and recognizing that this development indicates that decimation after the filter bank can be done without sacrificing the accuracy of the subsequent frequency estimate, and (iv) computations can be shared by using a detection statistic for the channel selection task that requires the computation of an intermediate result that can be reused during the frequency estimation step.
These reductions result in a method whose improved performance comes at the cost of a small increase in the computational complexity compared to Kay""s method. In particular, using a 2xc3x97-decimated four-channel filter bank, it is possible to achieve a frequency-independent threshold that is about 3 dB lower than the threshold exhibited by Kay""s method at frequencies near the middle of the frequency range. In addition, some of this additional computation can be done in parallel.
Recognizing that it is possible to repeatedly apply this method in a cascade fashion leads to a generalized approach using a filter bank having 4p channels, where p is the number of cascade stages. The number of additions and multiplies roughly doubles for each additional stage and the number of compares quadruples for each additional stage; however, the number of arctangents is halved for each additional stage cascaded. Because the complexity of computing an arctangent can be much greater than that of additions and multiplies, the burden of implementing a few stages of cascade is unlikely to be prohibitive in most cases. Thus, for a modest increase in complexity beyond the phase-based method of Kay it is possible to achieve performance close to that of the ML estimator. In a sense, the cascade method presents a system designer with a flexible xe2x80x9cdiscrete spectrumxe2x80x9d of design choices ranging from the low-complexity, low performance original phase-based method to the high-complexity, high performance cascaded filter bank method (whose performance tends toward that of the ML method as the number of stages increases).